package com.fengye.algorithms.leecode.dp;

/**
 * @Author fengye
 * @Date 2023/4/8 9:40
 **/
public class LongestPalindrome05 {

    public static void main(String[] args) {
        System.out.println(new LongestPalindrome05().longestPalindromeV2("abddb1"));
    }

    public String longestPalindromeV2(String s) {
        if (s.length() <= 2) {
            return s;
        }
        int start = 0;
        int maxLen = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            for (int j = i; j < s.length(); j++) {
                if (j - i < maxLen) {
                    continue;
                }
                if (isPalindrome(s, i, j)) {
                    if (maxLen < j - i + 1) {
                        start = i;
                        maxLen = j - i + 1;
                    }
                }
            }
        }
        return s.substring(start, start + maxLen);
    }

    public boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }

    public int longestPalindromeSubseq(String s) {
        int length = s.length();
        int[][] dp = new int[length][length];
        // i从最后一个开始遍历
        for (int i = length - 1; i >= 0; i--) {
            // 单个字符也是回文
            dp[i][i] = 1;
            // j从i的下一个开始
            for (int j = i + 1; j < length; j++) {
                // 递推公式
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j-1]);
                }
            }
        }

        return dp[0][length - 1];
    }

    public String longestPalindrome(String str) {
        String result = "";
        int[][] dp = new int[str.length()][str.length()];
        char c[] = str.toCharArray();

        for(int i=0;i<c.length;i++) {
            for(int j=i;j>=0;j--) {
                // 单个字符
                if(i-j<2 && c[i]==c[j]){
                    dp[j][i] = 1;
                } else if(c[i] == c[j] && dp[j+1][i-1]==1) {
                    dp[j][i] = 1;
                }
                if(dp[j][i]==1 && i-j+1 > result.length()) {
                    result = str.substring(j,i+1);
                }
            }
        }
        return result;
    }
}
